#include <iostream>
#include <initializer_list>
#include <string.h>
#include <vector>
#include <cassert>

namespace mini_stl
{
    template <class T>
    class vector
    {
    public:
        typedef T *iterator;
        typedef const T *const_iterator;
        vector() = default;

        // 支持初始化列表构造
        vector(std::initializer_list<T> init_list)
        {
            for (const auto &item : init_list)
            {
                emplace_back(item);
            }
        }

        vector(const mini_stl::vector<T> &v)
        {
            auto iter = v.begin();
            while (iter != v.end())
            {
                emplace_back(*iter++);
            }
        }

        vector(const T *array, size_t n)
        {
            for (int i = 0; i < n; i++)
            {
                push_back(array[i]);
            }
        }

        vector(size_t n, const T &val = T())
        {
            while (n--)
            {
                push_back(val);
            }
        }

        vector(int n, const T &val = T())
        {
            while (n--)
            {
                push_back(val);
            }
        }

        vector(int n, const T &&val)
        {
            while (n--)
            {
                push_back(val);
            }
        }

        void operator=(const mini_stl::vector<T> &v)
        {
            auto iter = v.begin();
            while (iter != v.end())
            {
                emplace_back(*iter++);
            }
        }

        // 迭代器构造
        template <class InputIterator>
        vector(InputIterator begin, InputIterator end)
        {
            while (begin != end)
            {
                push_back(*begin++);
            }
        }

        // 扩容
        void reserve(size_t capacity)
        {
            if (capacity > capacity_)
            {
                T *tmp = new T[capacity];
                if (tmp != nullptr)
                {
                    memcpy(tmp, start_, size_ * sizeof(T));
                    delete[] start_;
                    start_ = tmp;
                    end_ = start_ + size_;
                    finish_ = start_ + capacity_;
                    capacity_ = capacity;
                }
                else
                {
                    std::cerr << "alloc err\n";
                }
            }
        }

        void resize(size_t size, const T &val = T())
        {
            if (size > capacity_)
            {
                reserve(size);
            }
            if (size > size_)
            {
                while (end_ < start_ + size)
                {
                    *end_++ = val;
                }
            }
            else
            {
                end_ = start_ + size;
            }
        }

        iterator insert(iterator pos, const T &val = T())
        {
            assert(pos >= start_ && pos <= finish_);
            size_t n = pos - start_;
            CheckCapacity();
            pos = start_ + n;
            iterator cur = end_;
            while (cur > pos)
            {
                *cur = *(cur - 1);
                cur--;
            }
            *pos = val;
            ++end_;
            size_++;
            return pos;
        }

        iterator insert(iterator pos, const T &&val)
        {
            assert(pos >= start_ && pos <= finish_);
            size_t n = pos - start_;
            CheckCapacity();
            pos = start_ + n;
            iterator cur = end_;
            while (cur > pos)
            {
                *cur = *(cur - 1);
                cur--;
            }
            *pos = val;
            ++end_;
            size_++;
            return pos;
        }

        // emplace_back: 构造对象并将其插入到 vector 的末尾
        template <typename... Args>
        void emplace_back(Args &&...args)
        {
            push_back(T(std::forward<Args>(args)...));
        }
        template <typename... Args>
        void emplace(iterator pos, Args &&...args)
        {
            insert(pos, T(std::forward<Args>(args)...));
        }

        void push_back(const T &val = T())
        {
            insert(end_, val);
        }

        void push_back(const T &&val)
        {
            insert(end_, val);
        }

        void pop_back()
        {
            erase(end() - 1);
        }

        iterator erase(iterator pos)
        {
            assert(pos >= start_ && pos < end_);
            iterator cur = pos;
            while (cur < end_)
            {
                *cur = *(cur + 1);
                cur++;
            }
            --end_;
            size_--;
            return pos;
        }

        const_iterator begin() const
        {
            return start_;
        }

        const_iterator end() const
        {
            return end_;
        }

        iterator begin()
        {
            return start_;
        }

        iterator end()
        {
            return end_;
        }

        size_t size() const
        {
            return size_;
        }

        size_t capacity() const
        {
            return capacity_;
        }

        const T &back() const
        {
            return *(end() - 1);
        }

        // at: 返回指定索引位置的元素，并进行越界检查
        T &at(size_t index)
        {
            if (index >= size_)
            {
                throw std::out_of_range("Index out of range");
            }
            return start_[index];
        }

        bool empty() const
        {
            return size == 0;
        }

        ~vector()
        {
            delete[] start_;
            delete end_;
            delete finish_;
        }

    private:
        void CheckCapacity()
        {
            if (size_ == capacity_)
            {
                size_t newcapacity = capacity_ == 0 ? 4 : capacity_ * 2;
                T *tmp = new T[newcapacity];
                if (tmp != nullptr)
                {
                    memcpy(tmp, start_, size_ * sizeof(T));
                    delete[] start_;
                    start_ = tmp;
                    end_ = start_ + size_;
                    capacity_ = newcapacity;
                    finish_ = start_ + capacity_;
                }
                else
                {
                    std::cerr << "alloc err\n";
                }
            }
        }

    private:
        T *start_ = nullptr;  // 头指针
        T *end_ = nullptr;    // 尾指针
        T *finish_ = nullptr; // 容量指针
        size_t size_ = 0;
        size_t capacity_ = 0;
    };

};